The present invention relates to the field of instruction controlled digital computers and specifically to methods and apparatus associated with storage units in data processing systems.
It is common in data processing systems to have a memory hierarchy wherein buffer memories of relatively low capacity, but of relatively high speed, operate in cooperation with main memories of relatively high capacity but of relatively low speed. It is desired that the vast majority of accesses, either to fetch or store information, be from the buffer memory so that the overall access time of the system is enhanced. In order to have the vast majority of accesses come from the relatively fast buffer memory, information is exchanged between the main memory and the buffer memory in accordance with predetermined algorithms.
The efficiency with which a buffer memory works in decreasing the access time of the overall system is dependent on a number of variables. For example, the capacity of the buffer memory, the capacity of the main store, the data transfer rate between stores, the replacement algorithms which determine when transfers between the main store and buffer are made, and the virtual to real address translation methods and apparatus.
Typically, a buffer system consists of data, arranged in lines of bytes. Tags are used to indicate the origin of the data from within a large storage, such as main store. Data is transferred to and from main store a line at a time so all bytes in a line are either resident or not in the buffer. Based on this operation, a tag is associated with a line and indicates whether that entire line is present in the buffer or not. Thus, there is a one to one correspondence between tags and lines of data.
Buffer memories typically have more than one associativity of a given address to memory locations. With multiple associativities, there are two decisions which must be made in oder to complete a buffer access. First, a decision must be made as to whether the data is in the memory. Second, a decision must be made as to which one of the possible locations contains the data.
In the prior art, these decisions have been made by examining each associativity. In a case where there are N associativities, N matches are performed, one for each associativity, to determine whether or not the data is there for any associativity. If none of the N associativities finds a match, then the data is not there. If any associativity finds a match and thereby indicates that the data is there, then that indication also indentifies where the data is. In the prior art, both decisions have been made together after N matches of complete information for all N associativities.
Matches using complete information require a comparison of all the addressing and all the control information associated with a line of data. Such matches of complete information require a large amount of circuitry and tend to take excessive time. The problem is particularly severe in virtual addressing systems because in such systems the amount of address information and control information required is even greater than in real addressing systems. The translation information in a virtual system adds significantly to the amount of information included within the match process.
In accordance with the above background, problems exist in the amount of time required to do matches, particularly in virtual address systems. There is a need for improved memory systems which overcome these problems.